package com.clps.algorithm.chapter08.结点之和最大的路径;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

/**
 * 在二叉树中定义路径为从沿着结点间的连接从任意一个结点开始到达任意一个结点所经过的所有结点。路径中至少包含一个结点，
 * 不一定经过二叉树的根结点，也不一定经过叶结点。给你非空的一个二叉树，
 * 请求出二叉树所有路径上结点值之和的最大值。例如在图8.6中的二叉树中，从结点15开始经过结点20到达结点7的路径是结点值之和为42，是结点值之和最大的路径。
 */
public class demo01 {

    public static void main(String[] args) {

    }

    public int maxPathSum(TreeNode root){
        int[] maxSum = {Integer.MIN_VALUE};
        dfs(root,maxSum);
        return maxSum[0];
    }

    private int dfs(TreeNode root, int[] maxSum) {
        if(root == null){
            return  0;
        }

        int[] maxSumLeft = {Integer.MIN_VALUE};
        int left = Math.max(0,dfs(root.left,maxSumLeft));

        int[] maxSumRight = {Integer.MIN_VALUE};
        int right = Math.max(0,dfs(root.right,maxSumRight));

        maxSum[0] = Math.max(maxSumRight[0],maxSumRight[0]);
        maxSum[0] = Math.max(maxSumRight[0],root.val+left+right);
        return root.val+Math.max(left,right);
    }
}
